package com.leetcode.根据算法进行分类.排序算法相关.归并排序;

/**
 * @author: ZhouBert
 * @date: 2020/12/30
 * @description: 88. 合并两个有序数组
 * https://leetcode-cn.com/problems/merge-sorted-array/
 */
public class A_88_合并两个有序数组 {


	/**
	 * 这道题简直就是将归并排序中的 merge 部分完美地迁移出来！
	 * 这个设计是很巧妙的！
	 * 分析：
	 * 1.将 nums1 元素进行后移，直至数组头部空余出 n 个数量的位置；（这个做法很巧妙！）
	 * 2.将 nums1 和 nums2 的元素进行比较并依次放入 nums1
	 * @param nums1
	 * @param m
	 * @param nums2
	 * @param n
	 */
	public void merge(int[] nums1, int m, int[] nums2, int n) {
		//1.将 nums1 中的元素迁移到 begin=n 的位置
//		for (int i = 0; i < m; i++) {
//			nums1[i + n] = nums1[i];
//		}
		for (int i = m - 1; i >= 0; i--) {
			nums1[i + n] = nums1[i];
		}


		//begin 索引
		int mb = n, nb = 0, cb = 0;
		int size=m+n;

		while (mb < size && nb < n) {
			if (nums1[mb] > nums2[nb]) {
				nums1[cb++] = nums2[nb++];
			} else {
				nums1[cb++] = nums1[mb++];
			}
		}
		//如果 nums1 中的元素已经排好
		if (mb == size) {
			//将 nums2 中的元素完全覆盖
			while (nb < n) {
				nums1[cb++] = nums2[nb++];
			}
		}
	}


	public static void main(String[] args) {

	}

}
